package problem427;

//427.建立四叉树
//https://leetcode.cn/problems/construct-quad-tree/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public Node construct(int[][] grid) {
        //                    左上方顶点的坐标, 边长
        return createTree(grid, 0, 0, grid.length - 1);
    }

    public Node createTree(int[][] grid, int x, int y, int len) {
        Node node = null;
        if(check(grid, x, y, len)) {
            boolean val = grid[x][y] == 1 ? true : false;
            node = new Node(val, true);
        }else {
            int m = len / 2;
            node = new Node();
            node.isLeaf = false;
            node.topLeft = createTree(grid, x, y, m);
            node.topRight = createTree(grid, x, y+m+1, m);
            node.bottomLeft = createTree(grid, x+m+1, y, m);
            node.bottomRight = createTree(grid, x+m+1, y+m+1, m);
        }
        return node;
    }

    public boolean check(int[][] grid, int x, int y, int len) {
        int t = grid[x][y];
        for(int i = x; i<=x+len; i++) {
            for(int j = y; j<=y+len; j++) {
                if(t != grid[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}